/**
 * Implimentação do heap.
 *
 */

#include <stdlib.h>
#include <string.h>

#include "heap.h"

/*****************************************************************************
 *                                                                            *
 *  Defnindo Macros para uso interno                     .                    *
 *                                                                            *
 *****************************************************************************/

#define heap_parent(npos) ((int)(((npos) - 1) / 2))

#define heap_left(npos) (((npos) * 2) + 1)

#define heap_right(npos) (((npos) * 2) + 2)

/**
 * Inicializa o Heap
 * *compare função comparador
 * *destroy função usada para liberar cada nodo (*data) do heap.
 *
 */
void heap_init(Heap *heap,
		int (*comparator)(const void *key1, const void *key2),
		void (*destroy)(void *data)) {

	heap->size = 0;
	heap->compare = comparator;
	heap->destroy = destroy;
	heap->tree = NULL;

	return;

}

/**
 * Função para destruir o heap.
 */

void heap_destroy(Heap *heap) {

	int i;

	/**
	 * Remove todos os nodos do heap.
	 */
	if (heap->destroy != NULL) {

		for (i = 0; i < heap_size(heap); i++) {

			heap->destroy(heap->tree[i]);
		}

	}

//libera estrutura
	free(heap->tree);

//por precaução
	memset(heap, 0, sizeof(Heap));

	return;

}

/**
 * Insere o dado no heap
 * *heap estrutura heap no qual *data sera inserido.
 * Retorna -1 caso tenha algum erro, 0 caso tenha ocorrido tudo corretamente.
 *
 */
int heap_insert(Heap *heap, const void *data) {

	void *temp;

	int ipos, ppos;

//alocando o espaço para o nodo
	if ((temp = (void **) realloc(heap->tree,
			(heap_size(heap) + 1) * sizeof(void *))) == NULL) {

		return -1;

	}

	else {

		heap->tree = temp;

	}

//inserindo o nó após o ultimo

	heap->tree[heap_size(heap)] = (void *) data;

//realizando o heap, empurrando o conteudo do novo nó para cima.
	ipos = heap_size(heap);
	ppos = heap_parent(ipos);

	while (ipos > 0 && heap->compare(heap->tree[ppos], heap->tree[ipos]) < 0) {

		//realizando o swap entre o nó corrente e seus parentes.
		temp = heap->tree[ppos];
		heap->tree[ppos] = heap->tree[ipos];
		heap->tree[ipos] = temp;

		//movendo um nivel e continuar a fazer o heap
		ipos = ppos;
		ppos = heap_parent(ipos);

	}

//ajustando o tamanho do heap para adicionar o novo nodo
	heap->size++;

	return 0;

}

/**
 * Extrai o elemento *data do *heap
 * retorna -1 caso tenha algum erro na remoção.
 * 0 caso tenha removido com sucesso.
 */

int heap_extract(Heap *heap, void *data) {

	void *save, *temp;

	int ipos, lpos, rpos, mpos;

//não é permitido a remoção de um heap vazio
	if (heap_size(heap) == 0)
		return -1;

//extrai o no em cima do heap
	data = heap->tree[0];

//configura o tamanho usado para alocar o heap
	save = heap->tree[heap_size(heap) - 1];

	if (heap_size(heap) - 1 > 0) {

		if ((temp = (void **) realloc(heap->tree,
				(heap_size(heap) - 1) * sizeof(void *))) == NULL) {

			return -1;

		}

		else {

			heap->tree = temp;

		}

		//configura o tamanho do heap para levar em conta o nó removido
		heap->size--;

	}

	else {
		//operações para remover o ultimo nó.
		free(heap->tree);
		heap->tree = NULL;
		heap->size = 0;
		return 0;

	}

	//copia o ultimo nó para o topo.
	heap->tree[0] = save;

	//realizando a operacao de heap empurrando os conteudos de cima para baixo
	ipos = 0;
	lpos = heap_left(ipos);
	rpos = heap_right(ipos);

	while (1) {

		//escolhendo o filho para realizar a mudanca com o nó corrente
		lpos = heap_left(ipos);
		rpos = heap_right(ipos);

		if (lpos < heap_size(heap)
				&& heap->compare(heap->tree[lpos], heap->tree[ipos]) > 0) {

			mpos = lpos;

		}else {

			mpos = ipos;

		}

		if (rpos < heap_size(heap)
				&& heap->compare(heap->tree[rpos], heap->tree[mpos]) > 0) {

			mpos = rpos;

		}

		//quando mpos for igual a ipos a propriedade do heap foi restaurada.
		if (mpos == ipos) {

			break;

		} else {

			//realiza a mudanca entre o nó correte e o só selecionado.
			temp = heap->tree[mpos];
			heap->tree[mpos] = heap->tree[ipos];
			heap->tree[ipos] = temp;

			//move um nivel na arvore e continua a realizar o heap.
			ipos = mpos;

		}

	}

	return 0;

}
